package cc.ccoke.algorithms.primary.chapter02;

import cc.ccoke.algorithms.util.ArrayUtils;


/**
 * 堆排序
 * @author ccoke
 */
public class HeapSort {

    /**
     * 将数组转换为大根堆
     */
    public static void heapInsert(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int currentIndex = i;
            // 当前节点大于根节点时
            while (arr[currentIndex] > arr[(currentIndex - 1) / 2]) {
                int rootIndex = (currentIndex - 1) / 2;
                ArrayUtils.swap(arr, currentIndex, rootIndex);
                currentIndex = rootIndex;
            }
        }
    }

    /**
     * 调整大根堆
     */
    public static void heapify(int[] arr, int heapSize) {
        // 将节点与自身、左节点、右节点比较，将最大的放到节点上
        int currentIndex = 0;
        int leftIndex = currentIndex * 2 + 1;
        while (leftIndex < heapSize) {
            // 获取右节点
            int rightIndex= leftIndex + 1;
            // 寻找值最大节点
            int maxIndex = currentIndex;
            if (arr[maxIndex] < arr[leftIndex]) {
                maxIndex = leftIndex;
            }
            if (rightIndex < heapSize && arr[maxIndex] < arr[rightIndex]) {
                maxIndex = rightIndex;
            }
            // 如果最大的节点为自身，则停止
            if (maxIndex == currentIndex) {
                break;
            }
            ArrayUtils.swap(arr, currentIndex, maxIndex);
            currentIndex = maxIndex;
            leftIndex = currentIndex * 2 + 1;
        }
    }


    public static void main(String[] args) {
        int[] arr = ArrayUtils.generateByInt(10, 20);
        System.out.println("--- before ---");
        ArrayUtils.print(arr);
        System.out.println("--- after ---");
        // 将数组转换为大根堆后可以确定index=0的值是最大的
        heapInsert(arr);
        // 将最大值交换到最后，并将heapSize - 1
        int heapSize = arr.length;
        ArrayUtils.swap(arr, 0, -- heapSize);
        //修改大根堆
        while (heapSize > 0) {
            heapify(arr, heapSize);
            ArrayUtils.swap(arr, 0, -- heapSize);
        }
        ArrayUtils.print(arr);
    }

}
